package 动态规划.可dp可二分;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/5 15:19
 */
public class leetcode410 {
    /*
     复习该题时, 请注意一下,该题的 评论区, 要比 题解区精彩的 多!
     这个二分 真的 有点抽象!
     */


    public static int minMaxSolution(int[] nums, int k) {
        int len = nums.length;
        int [] preSum = new int [len + 1];
        for(int i = 0;i < len;i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        return minMax(0,k,len,preSum);
    }

    /**
     * 分成 k 组之后， 求  min {  max{ans1{.......}}, max{ans2{......}} ,.......}
     * 求 min { max { ...... } }
     * 这写的 不对!
     */
    public static int minMax(int index,int k,int len,int [] preSum) {
        if(index == len)
            return k == 0 ? 0 : Integer.MAX_VALUE;
        // 可以 直接 省略这个 但是 还是加上吧 少走一些弯路 明白原理是什么,即使 不用 这个 basecase 的话 index 也会控制 结束条件， 只不过夺走了一些路！
        if(k == 0)
            return Integer.MAX_VALUE;
        int ans = Integer.MAX_VALUE;
        for(int scale = 1;index + scale  <= len;scale++) {
            ans = Math.min(ans, Math.max(preSum[index + scale] - preSum[index], minMax(index + scale,k - 1,len,preSum)));
        }
        return ans;
    }

    /**
     * 将上面的 暴力 递归改写写成动态规划！
     * @return
     */
    public static int dp(int []nums,int k){
        int len = nums.length;
        int[][] dp = new int [len + 1][k + 1];
        // 前缀和数组
        int preSum [] = new int [len + 1];
        for(int i = 0;i <len; i++){
            preSum[i + 1] = nums[i] + preSum[i];
        }
        for(int i = 0;i <= len;i++){
            dp[i][0] = Integer.MAX_VALUE;
        }
        for(int i = 0;i <= k;i++){
            dp[len][i] = Integer.MAX_VALUE;
        }
        // 非常关键的一个 basecase
        dp[len][0] = 0;
        for(int index = len - 1;index >= 0;index--){
            for(int j = 1;j <= k;j++){
                int ans = Integer.MAX_VALUE;
                for(int scale = 1;scale + index <= len;scale++){
                    ans = Math.min(ans,Math.max(preSum[index + scale] - preSum[index],dp[index + scale][j - 1]));
                }
                dp[index][j] = ans;
            }
        }
        return dp[0][k];
    }

    public static void main(String []args){
        int nums[] = {7,2,5,10,8};
        int k = 3;
        System.out.println(minMaxSolution(nums,k));
        System.out.println(dp(nums,k));
        System.out.println(solutionNew(nums,k));
    }

    /*
     2023/3/12
     */

    /*
     这种想法 是正确的! 而且 比上面的想法 更加的 优雅!
     */
    public static int solutionNew(int nums[],int m){
        int preSum[] = new int[nums.length + 1];
        for(int i = 0;i < nums.length;i++){
            preSum[i + 1] = preSum[i] + nums[i];
        }
        int i = recursionNew(0, m, nums, preSum);
        return i;
    }

    public static int recursionNew(int index,int m,int nums[],int []preSum){

        if(index == nums.length && m == 0){
            return 0;
        }
        if(index == nums.length|| m == 0){
            return preSum[nums.length];
        }
        int min = preSum[nums.length];
        int max = 0;
        // 枚举 分组
        for(int i = index + 1; i <= nums.length;i++){
            max = Math.max(preSum[i] - preSum[index],recursionNew(i,m - 1,nums,preSum));
            min = Math.min(min,max);
        }
        return min;


    }
//    @Override



    @Test
    public void test() throws InterruptedException {
        System.out.println(Integer.parseInt("10"));
//        BufferedReader br = new BufferedReader();
//        br.readLine()
    }


    /*
     f(index, m) : 表示 从 index ~ len 分成 m 个 连续的子数组 的 和 的最大值的最小!
     */
    public int recursion(int index,int m,int nums[],int preSum[],Integer dp[][]){
        if(index == nums.length && m == 0){
            return 0;
        }
        if(index == nums.length || m == 0){
            return Integer.MAX_VALUE;
        }
        if(dp[index][m] != null){
            return dp[index][m];
        }
        int ans = Integer.MAX_VALUE / 2;
        for(int i = index;i < nums.length;i++){
            ans = Math.min(ans,Math.max(recursion(i + 1,m - 1,nums,preSum, dp),preSum[i + 1] - preSum[index]));
        }
        return  dp[index][m] = ans;
    }
    public int solve(int nums[],int k){
        int preSum[] = new int[nums.length + 1];
        for(int i = 0;i < nums.length;i++){
            preSum[i + 1] = preSum[i] + nums[i];
        }
        Integer dp[][] = new Integer[nums.length + 1][k + 1];
        return recursion(0,k,nums,preSum,dp);
    }

    @Test
    public void test1(){
        int nums[] = {7,2,5,10,8} ,k = 2;
        System.out.println(solve(nums, k));
        System.out.println(solutionNew(nums,k));
        System.out.println(binarySolve(nums,k));
        System.out.println(split(nums,10));
    }


    public int binarySolve(int nums[],int k){
         // [1 , 4, 4] 如果 l = 0 开始算的话, 这就是错误的!
//        int l = 0, r = 1000000000; // 这里要注意 一个点, 这里范围 为了偷懒直接范围 最大化, 在某些题的一个情况下, 可能会有些 问题在里面!
        int l = Arrays.stream(nums).max().getAsInt(), r = 1000000000; //  所以有时候 要非常准确的分析一下 ,这个取值范围!
        while(l < r){
            int mid = l + r >> 1;
            if(split(nums,mid)  <= k){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }



    public int split(int nums[],int compare){
        int sum = 0, count = 0;
        for(int i = 0;i < nums.length;i++){
            if(sum + nums[i] <= compare){
                sum += nums[i];
            }else{
                sum = nums[i];
                count++;
            }
        }
        return count + 1;
    }
}
